package array;

import java.util.*;

public class FindKPairsWithSmallestSums373 {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            PriorityQueue<List<Integer>> queue = new PriorityQueue<List<Integer>>((o1, o2) -> {
                return o2.get(0) + o2.get(1) - (o1.get(0) + o1.get(1));
            });

            for (int i = 0; i <  Math.min(k, nums1.length); i++) {
                for (int j = 0; j < Math.min(k,nums2.length); j++) {
                    if (queue.size() == k) {
                        List<Integer> peek = queue.peek();
                        if (nums1[i] + nums2[j] < peek.get(0) + peek.get(1)) {
                            queue.poll();
                            queue.add(Arrays.asList(nums1[i], nums2[j]));
                        }
                    } else {
                        queue.add(Arrays.asList(nums1[i], nums2[j]));
                    }
                }
            }
            return new ArrayList<>(queue);
        }
}
